Search operations involving regular expressions are employed in various applications including, for example, intrusion detection systems (IDS), virus detection, policy-based routing functions, internet and text search operations, document comparisons, and so on. A regular expression can simply be a word, a phrase, or a string of characters. For example, a regular expression including the string “gauss” would match data containing gauss, Gaussian, degauss, etc. More complex regular expressions include metacharacters that provide certain rules for performing the match. Some common metacharacters are the wildcard “.”, the alternation symbol “|”, and the character class symbol “[ ].” Regular expressions can also include quantifiers such as “*” to match 0 or more times, “+” to match 1 or more times, “?” to match 0 or 1 times, {n} to match exactly n times, {n,} to match at least n times, and {n,m} to match at least n times but no more than m times. For example, the regular expression “a.{2}b” will match any input string that includes the character “a” followed by exactly two instances of any character followed by the character “b” including, for example, the input strings “abbb,” adgb,” “a7yb,” “aaab,” and so on.
Traditionally, regular expression searches have been performed using software programs described by a sequence of instructions to be executed by one or more processors, for example, associated with a network search engine. For example, one conventional search technique that can be used to search an input string of characters for multiple patterns is the Aho-Corasick (AC) algorithm. The AC algorithm locates all occurrences of a number of patterns in the input string by constructing a finite state machine that embodies the patterns. More specifically, the AC algorithm constructs the finite state machine in three pre-processing stages commonly referred to as the goto stage, the failure stage, and the next stage. In the goto stage, a deterministic finite state automaton (DFA) or search tree is constructed for a given set of patterns. The DFA constructed in the goto stage includes various states for an input string, and transitions between the states based on characters of the input string. Each transition between states in the DFA is based on a single character of the input string. The failure and next stages add additional transitions between the states of the DFA to ensure that a string of length n can be searched in exactly n cycles. More specifically, the failure and next transitions allow the state machine to transition from one branch of the tree to another branch that is the next best (i.e. the longest) match in the DFA. Once the pre-processing stages have been performed, the DFA can then be used to search any input string for all of the deterministic patterns in the pattern set.
The foregoing describes search operations consistent with a DFA search tree implemented using a deterministic finite automaton state machine. Additionally, search operations using a series of instructions can also be similarly described. For example, each transition between states in the DFA can be represented as an instruction pertaining to a single character of the input string. Additional instructions describe the failure stage transitions and next stage transitions. More specifically, the instructions corresponding to the failure stage transitions and next stage transitions allow the execution of the series of instructions to transition from one instruction to another instruction that is the next best (i.e. the longest) match in the corresponding DFA.
One problem with prior string search engines using the AC algorithm is that that they are not well suited for performing wildcard or inexact pattern matching. As a result, some search engines complement the deterministic aspects of an AC search technique with a nondeterministic finite automaton (NFA) engine that is better suited to search input strings for inexact patterns, particularly those that include quantifiers such as “*” to match 0 or more times, “+” to match 1 or more times, “?” to match 0 or 1 times, {n} to match exactly n times, {n,} to match at least n times, and {n,m} to match at least n times but no more than m times.
For example, commonly-owned U.S. Pat. No. 7,539,032 discloses a content search system that implements search operations for regular expressions that specify one or more exact patterns and one or more inexact patterns by delegating exact pattern search operations to a DFA engine that is dedicated to perform exact pattern search operations and by delegating inexact pattern search operations to an NFA engine that is dedicated to perform inexact pattern search operations, where the match results of the exact pattern search operations and the match results of the inexact pattern search operations are combined to generate a result code that indicates whether an input string matches one or more regular expressions specifying the exact and inexact patterns.
FIG. 1A depicts a content search system 100 of the type disclosed in commonly-owned U.S. Pat. No. 7,539,032, which is incorporated by reference herein. More specifically, content search system 100 includes a system interface 110, a DFA engine 120, a data management unit 130, an NFA engine 140, and a result engine 150. The system interface 110 facilitates communication between search system 100 and an external network (e.g. the Internet), and is coupled to data management unit 130. More specifically, data management unit 130 receives input strings from the network via the system interface 110, selectively forwards portions of input strings to DFA engine 120 and/or NFA engine 140 for search operations, and coordinates communication between DFA engine 120, NFA engine 140, and result engine 150.
The data management unit 130 selectively forwards portions of input strings (e.g. regular expressions, or sub-expressions of regular expressions) to the DFA engine 120 or the NFA engine 140, depending in part on if the sub-expression 114 is an exact match sub-expression associated with an exact pattern (e.g. an exact sub-expression), or if the sub-expression is an inexact match sub-expression associated with an exact pattern (e.g. inexact sub-expression 116).
As disclosed in U.S. Pat. No. 7,539,032, the DFA engine 120 is configured to perform exact string match search operations to determine whether an input string contains exact patterns specified by one or more regular expressions, and the NFA engine 140 is configured to perform an inexact string match search operation to determine whether the input string contains one or more inexact patterns specified by one or more regular expressions. More specifically, the DFA engine 120 is implemented according to the AC algorithm, and the NFA engine 140 is implemented using various circuits (e.g. microprocessors, microcontrollers, programmable logic such as FPGAs and PLDs) that can execute microprograms that embody the inexact patterns to be searched for.
The result engine 150 includes a plurality of storage locations each for storing a result code that contains, for example, one or more match ID (MID) values, one or more trigger bits, and one or more microprogram indices. Each MID value identifies a corresponding exact pattern stored in the DFA engine that is matched by the input string, each trigger bit indicates whether the exact pattern identified by a corresponding MID value is part of a regular expression that requires inexact pattern search operations to be performed by the NFA engine, and each microprogram index can be used by the NFA engine to retrieve a microprogram that contains commands for implementing the inexact pattern search operation.
Referring to the microprogram that contains commands for implementing the inexact pattern search operation, such a microprogram can be implemented using conventional load/modify/store operations (e.g. using hardware register resources addressable by a microprogram instruction), or such a microprogram can be implemented using specialized instructions that are executed using NFA-related hardware resources addressable by a microprogram instruction. In either case, a system for inexact pattern searches involving a microprogram may include an instruction cache and an engine for managing such an instruction cache.
A significant limitation of search engines that use an instruction cache in combination with a microcontroller (i.e. a microprogram execution unit) to execute instructions of a microprogram that embodies an NFA sub-expression is that the instructions are typically stored in a random manner in memory, without regard to the sequence of state transitions of the underlying NFA search tree. As a result, sequentially executed instructions associated with implementing an NFA search operation may be distally located in the memory, thereby rendering instruction pre-fetching and caching relatively useless because of the large percentage of instruction cache misses during execution of the instructions.
For example, FIG. 1B depicts an NFA graph for a regular expression R1=“a(bc)?de” and a conventional instruction set 150 that can be executed by the NFA engine of FIG. 1A to implement search operations for R1. For an input string to match the regular expression R1, the input string must include the character “a” followed by zero or more instances of either the characters “b” or “c” followed by the characters “d” and “e”. To implement the search operation, the NFA engine 140 first fetches the instruction corresponding to the root node S0. As indicated in instruction set 150 of FIG. 1B, the first instruction 151(0) is located in an associated instruction memory (not shown for simplicity) at address N and includes the op-code “a” and next instruction addresses N+1 and N+3. Thus, if the NFA engine 140 determines a match between the first input character and the op-code “a” at S0, the NFA engine 140 fetches the two instructions 151(1) and 151(3) located at addresses N+1 and N+3 because a match on “a” at state S0 results in the simultaneous activation of states S1 and S3 to look for the characters “b” and “d”, respectively, in the next search cycle. Then, the NFA engine 140 sequentially executes the instructions located at addresses N+1 and N+3. If there is a match with character “b” at state S1, then the NFA engine 140 fetches the instruction 151(2) located at address N+2 to transition the state machine to state S2, and if there is a match with character “d” at state S3, then the NFA engine fetches the instruction 151(4) located at address N+4 to transition the state machine to state S4.
When the NFA engine 140 fetches the instructions 151(1) and 151(3) in response to a character match at state S0, two separate read operations to the instruction memory are typically used because the instructions are not stored in successive locations in the instruction memory. More specifically, because the two instructions 151(1) and 151(3) are sequentially executed but not stored in sequential locations in the instruction memory, instruction pre-fetching operations are typically ineffective because a number of other instructions would be fetched but not executed in the next search operation. This problem is exacerbated for more complex regular expressions that include hundreds of instructions that are not stored in the instruction memory according to their order of execution.
Further, in a system for inexact pattern searches involving a microprogram that contains commands for implementing the inexact pattern search operation, a microprogram based on conventional load/modify/store operations may be long and/or large (i.e. contain a large number or instructions), and/or may contain many conditional branches. These two characteristics hinder high-performance instruction caching. For example, if a microprogram based on conventional load/modify/store operations is large, then the instruction cache may have to be as equally as long and/or large to contain the entire microprogram. Alternatively, even if the engine for managing the instruction cache is capable of performing speculation, for example speculation that a particular branch will be taken (or not taken), the likelihood of such speculation being correct for each branch prediction varies inversely with the length of the microprogram. Moreover, the complexity of an engine for managing the instruction cache increases as the complexity of the inexact pattern search increases.
Thus, there is a need for a content search system that can capitalize on microprogram-based NFA search techniques with compact representation and high-performance use of instruction cache resources.
Like reference numerals refer to corresponding parts throughout the drawing figures.